// const arr = [99, -1, 2, 10, 8];
// // [ -1, 10, 2, 8, 99 ]

// // arr.sort() 按首字母排序
// console.log(arr.sort(function (a, b) {
//     return b - a;
// }));

// Chrome V8引擎
// 8个数以内 是插入排序
// 8个数以上是快速排序

// const arr1 = [
//     {
//         name: 'zhangsan',
//         age: 18,
//     },
//     {
//         name: 'lisi',
//         age: 190,
//     },
//     {
//         name: 'wangmazi',
//         age: 99,
//     },
//     {
//         name: 'fangyunchuan',
//         age: -1,
//     },
// ];

// console.log(arr1.sort(function (a, b) {
//     return b.age - a.age;
// }));

// 希尔排序
const arr1 = [1, 5, 2, 7, 45, 1, 53, 4, 6, 50];

// 变异冒泡
function pop (arr) {
    const res = [];
    while (arr.length > 0) { // N
        // 第一轮
        let maxIdx = 0;
        for (let i = 0; i < arr.length; i++) {  // N ~ 1
            const item = arr[i];
            if (item > arr[maxIdx]) {
                maxIdx = i;
            }
        }
        const max = arr.splice(maxIdx, 1)[0];
        res.unshift(max);
    }

    return res;
}

// console.log(pop(arr1));

// 快速排序
function quickSort (arr) {
    if (arr.length < 2) {
        return arr;
    }
    // 取标志位
    const flag = arr[0];
    // 左右数组
    const left = [];
    const right = [];
    // 循环比较
    for (let i = 1; i < arr.length; i++) {
        const item = arr[i];
        if (item > flag) {
            right.push(item);
        } else {
            left.push(item);
        }
    }
    // left   flag   right
    return [...quickSort(left), flag, ...quickSort(right)];
}

// console.log(quickSort(arr1));
function shellSort(arr) {
    let gap = Math.floor(arr.length / 2); //获取间隔
    while (gap >= 1) { // 判断间隔是否大于等于1，防止间隔gap为负数，出界
        for (let i = gap; i < arr.length; i++) {
            let tmp = arr[i];
            let j = i;
            while (arr[j - gap] > tmp && j > gap - 1) { // 间隔数组中前面一项和后面一项进行比较。j > gap - 1，如果gap等于1；间隔为1，整个排完的数组只差最后一步，前后两项插入排序。
                arr[j] = arr[j - gap];
                j -= gap; //111  为了让每个分割的小数组的前一项拿到后一项的值。
            }
            arr[j] = tmp; //与111 联系
        }
        gap = Math.floor(gap / 2);
    }
    return arr;
}

console.time('冒泡');
for (let i = 0; i < 1000000; i++) {
    pop(arr1);
}
console.timeEnd('冒泡');

console.time('希尔');
for (let i = 0; i < 1000000; i++) {
    shellSort(arr1);
}
console.timeEnd('希尔');

console.time('快速');
for (let i = 0; i < 1000000; i++) {
    quickSort(arr1);
}
console.timeEnd('快速');
